#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def uniquePaths(self, rows, cols):
        # 使用矩阵可以. 但是也可以使用滚动数组节省空间, 并且省去了初始化矩阵的麻烦.

        # method1 : 可以按行计算
        paths = [1] * cols
        for row in range(1, rows):
            for col in range(1, cols):
                # paths[row] = paths[row] + paths[row-1]
                paths[col] = paths[col] + paths[col-1]


        # method2 :可以按列计算
        # paths = [1] * rows
        # for col in range(1, cols):
        #     for row in range(1, rows):
        #         paths[row] = paths[row] + paths[row-1]

        return paths[-1]


def main():
    print("start main")
    s = Solution()
    # ret = s.uniquePaths(3, 3)
    # ret = s.uniquePaths(2, 2)
    # ret = s.uniquePaths(4, 4)
    ret = s.uniquePaths(4, 5)

    print(ret)

if __name__ == "__main__":
    main()
